The present invention is related to interactive entertainment products for advanced entertainment systems including computer entertainment systems, game consoles, hand held gaming devices and personal computers. More particularly, the present invention is directed towards the techniques that are employed for the generation of graphics and animations in such interactive entertainment products.
A large part of what users of current interactive game engines see is the play back of computer generated animations on a display. As users have been getting more sophisticated, they tend to demand ever more realistic computer generated animations. To this end, interactive game engines strive to play back animations at variable frame rates, while smoothly transitioning from animation to animation. Interactive game engines use interpolation to transition from one image frame to another and to mix several animations at once so that the game characters respond to the user's input continuously and without delay or even immediately.
At the graphics engine level, one way of keeping track of spatially varying features, such as the game character's limb positions, etc., is by using quaternions. A quaternion is an extension to normal complex numbers, composed of a real number and a vector and depends on one real and three imaginary units. Quaternions, a generalization of complex numbers having the form a+bi+cj+dk, where, a, b, c, and d are real numbers, and where i2=j2=k2=−1, were originally developed by the Irish mathematician, Sir William Rowan Hamilton. While interactive video games were not contemplated even by mathematical geniuses such as Sir Rowan in the 1840's, today, quaternions are commonly used in 3D graphics engines to represent rotations and orientations of coordinate axes. Using quaternions, it is possible to create smooth interpolations between two rotations. A rotation is, for example, the direction a game character or a game scene is pointing.
Qauternions have numerous advantages over other ways of representing rotations. They use less memory than matrices. Concatenation and inversion operations are fast. Conversion to other representations is also very fast. For these as well as other reasons, in an interactive game having complex characters, thousands of quaternions may be interpolated per frame.
A foundation of all these interpolations is the spherical linear interpolation (Slerp) function, which interpolates between two quaternions. The Slerp function is simple and mathematically robust, but it is a computationally expensive function. This limits its usefulness as game programmers call it (the Slerp function) only sparingly. In a complex animation engine where an abundance of blending is occurring, this function can become a computational “hot spot,” where the demand for such excessive computational resources may at best only be met by relatively few rather high-end processors, and at worst not be justifiable on the most typical processors.
It has long been established that one way for the reduction of computational hot spots is to use approximations instead of the actual computation of desired functions. However, approximations generally tend to speed things up at the expense of accuracy.
There is therefore a need for an accurate approximation to the Slerp function for interpolating quaternions, that is much faster to compute on current processors.